package com.work.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Given a string, find the length of the longest substring without repeating characters.
 * 超时
 * Created by suk on 2018/10/24.
 */
public class SubString_01_N3 {
    public static void main(String[] args) {
        SubString_01_N3 o = new SubString_01_N3();
        String s = "nfpdmpi";
        System.out.println(o.lengthOfLongestSubstring(s));
    }
    public int lengthOfLongestSubstring(String s) {
//        Map map = new HashMap();
        if (s.length() <= 1)
            return s.length();
        char[] chars  = s.toCharArray();
        List list = new ArrayList();
        int max = 0;
//        list.add(chars[i]);
        for (int i = 0; i < chars.length; i++) {
            if (!list.contains(chars[i])) {
                list.add(chars[i]);
                max = max > list.size() ? max :list.size();
            } else {
                max = max > list.size() ? max : list.size();
                int index = list.indexOf(chars[i]);
                if (index < list.size()) {

                    List tmp = new ArrayList();
                    list = list.subList(index + 1, list.size());
//                    list.clear();
//                    list.addAll(tmp);
                    list.add(chars[i]);
                }

            }
//            if (map.containsKey(chars[i])) {
//
//            }
        }
        return max;
    }
}
